\section{Introduction}
\label{sec:intro}

In this report we present an optimized parallel version of a 0-1 knapsack solver~\cite{knapsack} that is implemented using a Partitioned Global Address Space (PGAS) language, in particular, Unified Parallel C (UPC)~\cite{chauvin:05}.  We begin with a serial implementation of a dynamic programming solution to the 0-1 knapsack problem along with a naive parallel version.  We explain the main problem with this naive approach and then provide an optimized parallel version that improves upon the memory access and communication patterns of the original.